Recently, various standards have been developed for data communication over broadband wireless links. One such standard is set out in the IEEE 802.16 specifications and is commonly known as WiMAX. The specifications include IEEE 802.16-2004, primarily intended for systems having fixed subscriber stations, and IEEE 802.16e-2005 which among other things provides for mobile subscriber stations. In the following description, the term subscriber station (SS) applies to both fixed and mobile stations (SS/MS).
The entire content of IEEE Std 802.16-2004 “Air Interface for Fixed Broadband Wireless Access Systems” is hereby incorporated by reference. IEEE 802.16 envisages single-hop systems in which the subscriber station communicate directly with a base station within range, the range of a base station defining at least one “cell”. By deploying base stations at suitable positions within a given geographical area, and/or by providing multiple antennas in the same base station, a contiguous group of cells can be created to form a wide-area network. In this specification, the terms “network” and “system” will be used equivalently.
In systems of the above type, data is communicated by exchange of packets between the subscriber stations and base station whilst a connection (management connection or transport connection) is maintained between them. The direction of transmission of packets from the subscriber station to the base station is the uplink (UL), and the direction from the base station to the subscriber station is the downlink (DL). The packets have a defined format which follows a layered protocol applied to the system and its component radio devices. Protocol layers relevant to packets as such are the so-called physical layer (PHY) and media access layer (MAC). In the IEEE 802.16-2004 specification, these protocol layers form a protocol stack as shown in FIG. 1.
The media access layer shown in FIG. 1 is the protocol layer of most concern in the invention to be described. It is responsible for handling various functions including network access, bandwidth allocation, and maintaining connections. This includes controlling access of the BS and SS's to the network on the basis of “frames” which are the predetermined unit of time in the system, and which are divided in the time domain into a number of slots. Data is exchanged between the MAC peer entities, in other words, between the subscriber station and base station, in units of a protocol data unit (PDU), the PDU being conveyed across the PHY layer using a number of slots. Thus, a “slot” is a unit of time used for allocating bandwidth. The MAC is divided into sublayers including a security sublayer (see FIG. 1) for allowing authentication, key exchange and encryption of PDUs. These functions and sublayers can be roughly grouped into an “upper MAC” or UMAC, comprising the higher-level functions and a lower MAC or LMAC having the lower-level, more time-critical functions.
The UMAC is usually implemented by running software on a general purpose microprocessor, allowing re-programming when required for updates and system changes. Its functions include MAC management, the Service-Specific Conveyence Sublayer as shown in FIG. 1, and the MAC Common Part Sublayer (MAC CPS, see FIG. 1). The LMAC may also be provided by software executed by a processor but in this case, lower-level code (possibly embedded in the processor) and/or a real-time operating system are required. The LMAC acts as a bridge between the UMAC and the PHY, off-loading some of the task of UMAC by performing data encryption/decryption (functions of the Security Sublayer shown in FIG. 1), generation of error correction codes (CRC), PDU classification and FEC block processing as mentioned further below.
When considering transmission of data, data flow is generally from upper to lower levels in the protocol stack. Thus, for example, data packets (or so-called service data units, SDUs, described in more detail below) are transferred from a higher level in the protocol stack (an Application Layer, not shown in FIG. 1) via the CS SAP shown in FIG. 1. In the UMAC, the SDUs are organised into queues for transfer to the LMAC, where they are converted (in a process called “packing”) into MAC PDUs for constructing a subframe. Since the data sizes of SDUs and PDUs need not match, so-called “fragmentation” may also be required, in which a single SDU is split between multiple MAC PDUs. In the physical layer, the assembled subframe is prepared for transmission by assigning its constituent elements to one of a number of “bursts” of radio waves. FIG. 2 shows schematically the relationship between SDUs, PDUs and bursts.
In the bursts, Forward Error Correction (FEC) is used to help the receiver correct errors introduced by the transmission process. Each burst can include a plurality of FEC blocks as indicated in FIG. 2. The MAC PDUs are contained (in concatenated form) in the FEC blocks, and a MAC PDU may span FEC block boundaries.
Various physical layer implementations are possible in an IEEE 802.16 network, depending on the available frequency range and application; for example, a time division duplex (TDD) mode and a frequency division duplex (FDD) mode as described below. The PHY layer also defines the transmission technique such as OFDM (orthogonal frequency division multiplexing) or OFDMA (orthogonal frequency division multiple access), which techniques will now be outlined briefly.
In OFDM, a single data stream is modulated onto N parallel sub-carriers, each sub-carrier signal having its own frequency range. This allows the total bandwidth (i.e. the amount of data to be sent in a given time interval) to be divided over a plurality of sub-carriers thereby increasing the duration of each data symbol. Since each sub-carrier has a lower information rate, multi-carrier systems benefit from enhanced immunity to channel induced distortion compared with single carrier systems. This is made possible by ensuring that the transmission rate and hence bandwidth of each subcarrier is less than the coherence bandwidth of the channel. As a result, the channel distortion experienced on a signal subcarrier is frequency independent and can hence be corrected by a simple phase and amplitude correction factor. Thus the channel distortion correction entity within a multicarrier receiver can be of significantly lower complexity of its counterpart within a single carrier receiver when the system bandwidth is in excess of the coherence bandwidth of the channel.
An OFDM system uses a plurality of sub-carrier frequencies which are orthogonal in a mathematical sense so that the sub-carriers' spectra may overlap without interference due to the fact they are mutually independent. The orthogonality of OFDM systems removes the need for guard band frequencies and thereby increases the spectral efficiency of the system. OFDM has been proposed and adopted for many wireless systems. In an OFDM system, a block of N modulated parallel data source signals is mapped to N orthogonal parallel sub-carriers by using an Inverse Discrete or Fast Fourier Transform algorithm (IDFT/IFFT) to form a signal known as an “OFDM symbol” in the time domain at the transmitter. Thus, an “OFDM symbol” is the composite signal of all N sub-carrier signals. At the receiver, the received time-domain signal is transformed back to frequency domain by applying Discrete Fourier Transform (DFT) or Fast Fourier Transform (FFT) algorithm.
OFDMA (Orthogonal Frequency Division Multiple Access) is a multiple access variant of OFDM. It works by assigning a subset of the sub-carriers to an individual subscriber. This allows simultaneous transmission from several users leading to better spectral efficiency. However, there is still the issue of allowing bi-directional communication, that is, in the uplink and download directions, without interference.
In order to enable bi-directional communication between two nodes, two well known different approaches exist for duplexing the two (forward or downlink and reverse or uplink) communication links to overcome the physical limitation that a device cannot simultaneously transmit and receive on the same resource medium. The first, frequency division duplexing (FDD), involves operating the two links simultaneously but on different frequency bands by subdividing the transmission medium into two distinct bands, one for DL and the other for UL communications. The second, time division duplexing (TDD), involves operating the two links on the same frequency band, but subdividing the access to the medium in time so that only the DL or the UL will be utilizing the medium at any one point in time. Both approaches (TDD & FDD) have their relative merits and are both well used techniques for single hop wired and wireless communication systems. Although the IEEE802.16 standard incorporates both an FDD and TDD mode, the remainder of this description will refer to the TDD mode.
FIGS. 3 and 4 illustrate the TDD frame structure used in the OFDMA physical layer mode of the IEEE802.16 standard (WiMAX).
Referring first to FIG. 3, the frame can be considered to occupy a given length of time and a given frequency band, the time axis being denoted in FIG. 3 by “OFDMA symbol number”, and the frequency axis by “subchannel logical number” (each subchannel is a set of the sub-carriers referred to above). Each frame is divided into DL and UL subframes, each being a discrete transmission interval. They are separated by a Transmit/Receive and Receive/Transmit Transition Guard interval (TTG and RTG respectively). Each DL subframe starts with a preamble followed by the Frame Control Header (FCH), the DL-MAP, and the UL-MAP. The FCH contains the DL Frame Prefix (DLFP) to specify the burst profile and the length of the DL-MAP. The DLFP is a data structure transmitted at the beginning of each frame and contains information regarding the current frame; it is mapped to the FCH. Simultaneous DL allocations can be broadcast, multicast and unicast and they can also include an allocation for another BS rather than a serving BS. Simultaneous ULs can be data allocations and ranging or bandwidth requests.
FIG. 4 shows the OFDMA TDD frame structure from a different perspective, illustrating, within the UL-subframe, a packet format having two parts, a PHY header and a MAC PDU. The MAC PDU in turn consists of a MAC header, an optional payload, and optional error correction code (cyclic redundancy code or CRC). The PHY header includes training sequences, frequency band allocation information, and other information relating to physical layer parameters. Within the MAC PDU, the MAC header normally gives essential parameters for media access, such as the type of PDU, MAC address, and type of MAC signalling etc. The CRC within MAC PDU is optional, and can be used to check the received MAC PDU. The payload within MAC PDU is used to contain the data which the SS wishes to send to the BS, but is also optional. For example, some controlling messages, such as a bandwidth request, or an ACK message, have no payload. The payload could be data from higher layer, or sub-MAC-header, which can give additional MAC information.
Additionally, 802.16e OFDMA provides subchannelization as a means to better manage network performance to address specific coverage and capacity requirements. The OFDMA physical layer divides the available OFDM symbols and component sub-carriers (see FIG. 3) into distinct logical and physical subchannels, allowing multiple bursts to co-exist or overlap in the same time interval as shown in FIG. 3. On the downlink, a single burst may be shared by several users (subscriber stations) but on the uplink, each burst corresponds to a single user. OFDMA subchannelization techniques include Frequency Diverse and Frequency Selective Transmission schemes.
Frequency Diverse Transmission schemes can be grouped into Full Usage of Subchannels (FUSC) and Partial Usage of Subchannels (PUSC) modes. These modes support frequency diverse transmission, where the subcarriers assigned to each logical subchannel are pseudo-randomly distributed across the available subcarrier set. In FUSC, the subcarriers are scattered throughout the frequency range whereas in PUSC, several scattered clusters of subcarriers are used to form a subchannel. These schemes provide frequency diversity that is better suited to handle varying channel conditions and benefits network coverage and capacity.
Frequency Selective subchannelization is supported through the Band Adaptive Modulation and Coding (AMC) mode. Band AMC permits subchannel construction through physically adjacent subcarrier allocations, that is, contiguous groups of subcarriers. The system scheduler can utilize closed loop channel feedback techniques to determine the optimal subchannels to be allocated to each subscriber based on the unique channel conditions. FIG. 6 shows an OFDMA TDD mode frame structure including FUSC, PUSC and AMC zones. In general, FUSC and PUSC are more suitable for connections between a base station and mobile stations, with AMC being suitable for connections with fixed subscriber stations.
Subchannelization is of significance for frequency reuse schemes for allocation of frequencies among adjacent cells. Perhaps the most common reuse scheme is referred to as “reuse 3” (re-use factor 3): in this scheme, hexagonal cells are considered with each pair of adjacent cells being allotted a different set of frequency channels to reduce interference, three sets of channels being sufficient to achieve this. PUSC or FUSC is an appropriate transmission scheme in this case, since due to the random allocation of subcarriers to subchannels the possibility of interference between signals in different cells is further minimized. “Reuse 1”, on the other hand, simply means using the same set of frequencies in every cell (re-use factor 1). This tends to increase interference (reduce CINR) but allows the whole of the available frequency range (all subchannels in FIG. 3) to be used by each connection, and is simpler to implement in real-world systems. It is possible to employ different re-use schemes simultaneously for different subscribers in a single cell. In particular, Reuse 3 may be appropriate for users near the edges of a cell whilst Reuse 1 can be safely used for subscribers near the centre of a cell where interference from other cells is unlikely. This results in an “effective reuse factor” for the system of somewhere between 1 and 3. Conventionally, cells were each provided with a respective, centrally-located base station but increasingly, multiple directional antennas are mounted on a single base station to allow the same base station to serve a plurality of cells around itself.
The DL-subframe includes a broadcast control field with a DL-MAP and UL-MAP, by which the BS informs the receiving device of the frame structure. The MAP is a map of bandwidth allocation in the frame and consists of Information Elements (IE) each containing a connection ID. The map IEs inform subscriber stations to which burst(s) they have been assigned to receive information. Thus, in a TDD mode network, bandwidth allocation means the allocation of resources (slots) within frames. The DL-MAP and UL-MAP are examples of management messages broadcast by the BS (that is, transmitted to all subscribers). Other management messages include an Uplink Channel Descriptor UCD and Downlink Channel Descriptor DCD (both shown in FIG. 4), and Dynamic Service Request and Response (DS-REQ and -RSP) messages.
The concept of quality of service (QoS) is employed in wireless communication systems for allowing a wide range of services to be provided. Depending upon the kind of service being provided (see below), packets may need to be transmitted with a certain accuracy and/or within a certain time delay or they may be useless, and possibly require re-transmission. Thus, during communication with a subscriber station, the base station allocates a QoS level depending on the type of service requested by the subscriber station and available bandwidth, bearing in mind that the base station typically will be communicating with several subscriber stations simultaneously. The QoS parameters take into account priority of transmission (time delay or latency), accuracy of transmission (error rate) and throughput (data rate).
A connection between a base station and subscriber station (more precisely, between MAC layers in those devices—so-called peer entities) is assigned a connection ID (CID) and the base station keeps track of CIDs for managing its active connections. To support addressing and QoS control, some wireless communication systems put connection identification (CID) into a MAC header. For instance, in WiMAX, the service flow between SS/MS and BS can be created and activated during network entry procedure or by dynamic service flow procedure. As mentioned earlier, a service flow ID (SFID) will be assigned to each existing service flow, and each service flow is also associated with a specific QoS demand. A service flow has at least an SFID and an associated direction. The connection ID (CID) of the transport connection exists only when the service flow is admitted or active. The relationship between SFID and transport CID is unique, which means an SFID shall never be associated with more than one transport ID, and a transport CID shall never be associated with more than one SFID.
The BS uses a scheduler (scheduling algorithm) to manage the bandwidth (slot) allocations for all the currently-active connections, balancing the needs of the various subscribers. That is, each SS has to negotiate only once for network entry, after which it is allocated bandwidth by the BS which, though it may increase or decrease on request from the SS or under other demands on the network, remains assigned to that SS thus keeping the connection active.
The scheduler has to ensure, as far as possible, that all connections needing to be served within the current frame (in particular, the DL subframe being constructed in the base station) receive some resources (bandwidth). Aside from this QoS requirement, other factors to be taken into account include the distance (path loss) from the base station to each subscriber and the mobility, if any, of the subscriber. If a subscriber is far from the base station, or moving away, the feasible transmission rate on the downlink will be reduced so that it may be more efficient (in terms of system throughput) to give preference to subscribers closer to the base station. On the other hand, it is not acceptable for any subscribers to be starved of data.
One technique aiming to balance these factors is called the “proportional fair” algorithm. It seeks to achieve a balance between system throughput and fairness to subscribers by maximising the logarithms of long-term averaged data rates provided to all subscribers.
As already mentioned, each connection has a service class and an associated QoS. The QoS is allocated first during a network entry procedure (connection set-up phase) at the time the subscriber station joins the network, and may be modified subsequently by the subscriber station making a request to the base station whilst the connection is maintained. This may involve assigning additional bandwidth to the connection, perhaps repeatedly, depending on available resources in the network.
The relationship between QoS and CID/SFID is illustrated in FIG. 5. For ease of understanding FIG. 5, it is noted that “service flow” refers to transmission of data in a given direction (uplink or downlink) on a connection having a particular QoS. The QoS of the connection is defined by a service flow identifier (SFID) which has a one-to-one relationship to the connection ID. Strictly speaking, it is the service flow (or the connection) to which bandwidth is allocated, but it is convenient to think of bandwidth being assigned by the BS to the SS involved in the connection. Each service flow can be classified into one of a set of service classes or QoS classes. Although basically the same for both the DL and UL, these service classes are defined slightly differently from the point of view of the DL and UL scheduler. There are differences between the mechanism for QoS delivery on the DL and UL due to the fact the BS does not have direct visibility of the buffer status at the MS and may not know the packet error rate at the MS.
Downlink (DL)
The following service class types are defined in the IEEE 802.16:
                UGS: Unsolicited grant service        RT-VR: Real-time variable rate service        ERT-VR: Extended real-time variable rate service        NRT-VR: Non real-time variable rate service        BE: Best effort service        
Table 1 provides a brief description of the purpose and lists the parameters associated with each service class. These parameters are described in Table 2.
TABLE 1Overview of DL service types.TypePurposeAssociated parametersUGSSupport real-time applications generating fixed-rateTolerated jitterdata that require guaranteed delay and jitter. PDUMaximum sustained traffic ratelengths can be fixed or variable.Minimum reserved traffic rateMaximum latencyRequest/Transmission policyUnsolicited grant intervalRT-VRSupport real-time data applications generatingMaximum latencyvariable-rate data that require guaranteed rate andMinimum reserved traffic ratedelay.Maximum sustained traffic rateTraffic priorityRequest/transmission policy(Unsolicited polling interval)ERT-VRSupport real-time data applications generatingMaximum latencyvariable-rate data that required guaranteed rate,Tolerated jitterdelay and jitter.Minimum reserved traffic rateMaximum sustained traffic rateTraffic priorityRequest/transmission policyUnsolicited grant intervalNRT-VRSupport non-real-time applications generatingMinimum reserved traffic ratevariable-rate data that require guaranteed rate butMaximum sustained traffic rateinsensitive to delay.Traffic priorityRequest/transmission policyBESupport applications generating variable-rate dataMaximum sustained traffic ratewith no rate or delay requirements.Traffic priorityRequest/transmission policy
TABLE 2Parameter description.ParameterDefinitionMinimum reserved traffic rateMinimum rate measured at input of the CS.Maximum latencyMaximum time to deliver packet between CS andCS at peer.Maximum sustained traffic rateBound on maximum SDU data rate. Definition is leftto vendor implementation. SDUs deemed to exceedmay be delay or dropped.Request/transmission policyPDU formation attributes(fragment/pack/CRC/header suppression)Tolerated jitterMaximum delay variation.Traffic priorityWhen two service flows are identical in allparameters, traffic priority dictates which flow shouldtake precedence.Unsolicited polling intervalInterval between successive polling grantopportunities. Polling shall be performed with nojitter allowance.Unsolicited grant intervalInterval between successive data grantopportunities. Grant shall be made between intervaltime and interval time + tolerated jitter.
It is the role of the downlink packet scheduler to ensure that the requirements set for each active service flow, based on the configured parameter settings, are met.
Uplink (UL)
The following service class types and scheduling services are defined in the IEEE 802.16 standard and supported in the WiMAX Forum Mobile System Profile:                UGS: Unsolicited grant service        rtPS: Real-time polling service        ertPS: Extended real-time polling service        nrtPS: Non-real-time polling service        BE: Best effort service).        
Table 3 provides a brief description of the purpose and lists the parameters associated with each service class (note the description of the parameters is provided in Table 2).
TABLE 3Overview of UL service types.TypePurposeAssociated parametersUGSSupport real-time applications generating fixed-rateMaximum sustained traffic ratedata that requires guaranteed delay and jitter.Tolerated jitterProvides grants in unsolicited manner.Minimum reserved traffic rate(same as max. sustained rate)Maximum latencyRequest/Transmission policyUnsolicited grant intervalrtPSSupport real-time data applications generatingMaximum latencyvariable-rate data that require guaranteed rate andMinimum reserved traffic ratedelay. Provides periodic request opportunities.Maximum sustained traffic rateTraffic priorityRequest/transmission policyUnsolicited polling intervalertPSSupport real-time data applications generatingMaximum latencyvariable-rate data that required guaranteed rate,Tolerated jitterdelay and jitter. Provides grants in unsolicitedMinimum reserved traffic ratemanner.Maximum sustained traffic rateTraffic priorityRequest/transmission policyUnsolicited grant intervalnrtPSSupport non-real-time applications generatingMinimum reserved traffic ratevariable-rate data that require guaranteed rate butMaximum sustained traffic rateinsensitive to delay. Provides regular requestTraffic priorityopportunities.Request/transmission policyBESupport applications generating variable-rate dataMaximum sustained traffic ratewith no rate or delay requirements. Uses unicastTraffic priorityand contention request opportunities.Request/transmission policy
It is the role of the uplink packet scheduler to ensure that the requirements set for each active service flow, based on the configured parameter settings, are met by allocating resources for the MS CIDs appropriately. In particular in the case of the UL, the scheduler must also provide polling opportunities (enough BW to transmit a BW request) for the request of a grant to service flows with a polling interval (e.g. rtPS or nrtPS) or UGS connections with the PM bit set, or unsolicited grants based on the flow parameters.
In the UL the scheduler also needs to consider information received from the MS about its current requirements, these include:                PBR, PM, SI, FL & FLI bits in the grant management subheader (see below)        BR in the MAC signalling type I header (incremental or aggregate)        CDMA BW requestMore details of these items of information are given in the table below:        
FieldPurposeSI (UGS)Slip indicator: flag to indicate service flow has exceeded the transmit queue depth.BS should respond by increasing the grant size by 1%.PM (UGS)Poll me: For UGS connection indicates to issue a polling opportunity for anotherconnection. BS should grant BW to enable transmission of BR*.FL/FLI (UGS)Frame Latency: Number of frames ago that data was available. As long as FL isabove a certain threshold, the BS should respond by advancing the next grant time.BR/(PBR)Bandwidth request (piggybacked): BS should use the information to update the BWneeds of the connection.CDMA BRCDMA based BR: BS should respond with allocation for MS to issue BR (usingCDMA allocation IE)*.*Note BR message requires a 6 byte allocation.Supported Classes & Parameters
Table 4 indicates which parameters are mandatory, optional or not applicable for each service class:
TABLE 4Supported service class parameters by type.ParametersUGSRTERTNRTBEMin rateO*MMM—Max rateMMMMOMax latencyMMM——JitterM—O——Request/Transmission policyMMMMMUplink grant scheduling typeMMMMMTraffic priority—OOMOUnsolicited grant intervalO—O——Unsolicited polling interval (UL)—O———*Shall be set equal to the max rate
As will be apparent from the above description, the tasks of the UL and DL packet schedulers in a base station are considerably involved. However, for WiMAX systems to become successful commercially, base station functionality has to be provided at low cost. Consequently, there is a need to provide the above scheduling functions in a simple manner so as to minimise the processing capacity required and hence its cost.
More particularly, there is a need for a subsystem providing an LMAC scheduler and PDU builder in an efficient and cost-effective manner.